/*****没办法处理整数解，只能给出实数解********/
#include<bits/stdc++.h>

using namespace std;

const double eps=1e-6;
const int N=1000;
const int M=1000;
int n, m;   //n:方程个数 m:未知数
double a[N][M], b[M], c[N], ans;
void pivot(int l, int e) {
    //非基本变量的最紧约束转换
    b[l] /= a[l][e];
    for (int j = 1; j <= m; j++)
        if (j != e) a[l][j] /= a[l][e];
    a[l][e] = 1 / a[l][e];
    //重新计算矩阵
    for (int i = 1; i <= m; i++)
        if (i != l && fabs(a[i][e]) > 0) {
            b[i] -= a[i][e] * b[l];
            for (int j = 1; j <= n; j++)
                if (j != e) a[i][j] -= a[i][e] * a[l][j];
            a[i][e] = -a[i][e] * a[l][e];
        }
    //计算新的目标函数
    ans += c[e] * b[l];
    for (int j = 1; j <= n; j++)
        if (j != e) c[j] -= c[e] * a[l][j];
    c[e] = -c[e] * a[l][e];
}

double simplex() {
    while (true) {
        int e = 0, l = 0;
        for (e = 1; e <= m; e++)
            if (c[e] > eps) break;
        if (e == m + 1) return ans;
        double mn = INF;
        for (int i = 1; i <= n; i++)    //寻找最紧约束
            if (a[i][e] > eps && mn > b[i] / a[i][e]) mn = b[i] / a[i][e], l = i;
        if (mn == INF) return INF;
        pivot(l, e);
    }
}

int main() {

}
